package easy.按奇偶校验排序数组;

import org.junit.Test;

import java.util.ArrayList;
import java.util.LinkedList;

/*
给定一个非负整数数组A，返回一个由A的所有偶数元素组成的数组，后跟A的所有奇数元素。
您可以返回满足此条件的任何答案数组。

Example 1:
Input: [3,1,2,4]
Output: [2,4,3,1]
The outputs [4,2,3,1], [2,4,1,3], and [4,2,1,3] would also be accepted.
Note:
1 <= A.length <= 5000
0 <= A[i] <= 5000

 */
public class Solution {
    //用两个数组分别存奇数和偶数
    public int[] sortArrayByParity(int[] A) {
        ArrayList<Integer> even = new ArrayList<>();
        ArrayList<Integer> odd = new ArrayList<>();
        for (int i = 0; i < A.length; i++) {
            int result;
            result = A[i] % 2;
            if (result != 0) {
                odd.add(A[i]);
            } else
                even.add(A[i]);
        }
        even.addAll(odd);
        for (int i = 0; i < A.length; i++) {
            A[i]=even.get(i);
        }
        return A;
    }
    //双向链表实现
    public int[] sortArrayByParity2(int[] A) {
        LinkedList<Integer> res=new LinkedList<Integer>();
        for (int i = 0; i < A.length; i++) {
            int result = A[i] % 2;
            if (result != 0) {
                res.addLast(A[i]);
            } else
                res.addFirst(A[i]);
        }
        //将集合转换成int[]
        for (int j = 0; j <A.length; j++) {
            A[j]=res.get(j);
        }
        return A;
    }

    @Test
    public void test() {
        int[] ints = {3, 1, 2, 4};
        Solution solution = new Solution();
        int[] res = solution.sortArrayByParity2(ints);
        for (int i = 0; i < res.length; i++) {
            System.out.println(res[i]);
        }

    }
}
